#===============================================================================
# Note:
# This implementation solves the "Not Garbage" problem.
# This problem is the complement of the May-be-garbage problem.
# In the MBG problem, one looks for those variables which may be garbage,
# since we did not want to represent the set of all the variabled. We
# tracked it's complement.
# Yet, the May Be Garbage problem can be solved using this code by implementing
# one of the following:
# 1. If the user gives as input the set of variables in the program, we can
# return for each node the substraction between the set of variables and the
# "Not Garbage" variables set.
# 2. Doing some lexical analysis on the program we can find the set of variables
# and then do the substraction proposed in 1.
#===============================================================================

import re

bottom = "bottom"  # artifricial bottomalue to avoid the need to know the set of used expressions
top = set()
iota = set()

def join(a, b):
    if a == bottom:
        return b
    elif b == bottom:
        return a
    else: return a & b

def meet(a, b):
    if a == bottom:
        return bottom
    elif b == bottom:
        return bottom
    else: return a | b
    
def args(expr_tree):
    if len(expr_tree) == 0:
        return
    if is_var(expr_tree[0]):
        yield expr_tree[0]
    for subtree in expr_tree[1]:
        for children in args(subtree):
            yield children
                     
def assign(ng, lhs, e):
    if (set(args(e)) & ng) == set(args(e)):
        return ng | set([lhs])
    else:
        return ng - set([lhs])

def is_var(literal):
    return re.match("^[_a-z][_a-z0-9]*$", literal) is not None
